package com.njupt.DynamicProgramming;

import java.util.Scanner;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/1/27 16:22
 * @Description: 0 1背包问题
 * 考虑另一种解法 回溯遍历
 * @Version: 1.0
 */


public class KaMa_46_Carrying_Research_Materials {

    int maxValue = Integer.MIN_VALUE;

    int currentWeight;

    int currentValue;

    /**
     * 动态规划 二维数组
     *
     * @param weight
     * @param value
     * @param bagWeight
     * @return
     */
    public static int carryResearchMaterials(int[] weight, int[] value, int bagWeight) {
        int m = weight.length;
        int[][] dp = new int[m][bagWeight + 1];

        //dp数组初始化
        for (int j = weight[0]; j <= bagWeight; j++) {
            dp[0][j] = value[0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j <= bagWeight; j++) {
                if (j < weight[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(value[i] + dp[i - 1][j - weight[i]], dp[i - 1][j]);
                }
            }
        }
        return dp[m - 1][bagWeight];
    }


    /**
     * 一维数组，动态规划
     * @param weight
     * @param value
     * @param bagWeight
     * @return
     */
    public static int carryResearchMaterials_one_dim(int[] weight, int[] value, int bagWeight) {
        int[] dp = new int[bagWeight + 1];

        for (int i = 0; i < weight.length; i++) {  //先遍历物品
            for (int j = bagWeight; j >= weight[i]; j--) { //再遍历背包
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        return dp[bagWeight];
    }

    /**
     * 回溯枚举法
     *
     * @param startIndex
     * @param weight
     * @param value
     * @param bagWeight
     */
    public void carryResearchMaterials(int startIndex, int[] weight, int[] value, int bagWeight) {


        if (this.currentWeight > bagWeight) {
            return;
        }

        if (this.currentValue > this.maxValue) {
            this.maxValue = this.currentValue;
        }


        for (int i = startIndex; i < weight.length; i++) {
            this.currentWeight += weight[i];
            this.currentValue += value[i];
            carryResearchMaterials(i + 1, weight, value, bagWeight);
            this.currentWeight -= weight[i];
            this.currentValue -= value[i];
        }


    }

    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int m = sc.nextInt();
//        int bagWeight = sc.nextInt();
//
//        int[] weight = new int[m];
//
//        int[] value = new int[m];
//
//        for (int i = 0; i < m; i++) {
//            weight[i] = sc.nextInt();
//        }
//
//        for (int i = 0; i < m; i++) {
//            value[i] = sc.nextInt();
//        }

        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int bagWeight = 4;

        KaMa_46_Carrying_Research_Materials test = new KaMa_46_Carrying_Research_Materials();
        int maxValue = carryResearchMaterials_one_dim(weight, value, bagWeight);
//        test.carryResearchMaterials(0,weight,value,bagWeight);
        System.out.println(maxValue);

    }
}
